class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sizeOfNums = nums.size();
        if(sizeOfNums < 1 || sizeOfNums > 100000)  return 0;
        /*
        时间复杂度为O(n)的算法：举例分析数组的规律/动态规划；
        动态规划方程：f(i) = nums[i],  i = 0或f(i - 1) <= 0;
                     f(i) = f(i - 1) + nums[i],  i != 0且f(i - 1) > 0
        */
        int sum = 0;
        int pivot = nums[0];
        for(int i = 0; i < sizeOfNums; ++i){
            //若前面数组之和小于0,重新计数
            if(sum <= 0)  sum = nums[i];
            else  sum += nums[i];
            if(sum > pivot)  pivot = sum;
        }

        return pivot;
    }
};